package bite;

import java.util.ArrayList;
import java.util.Scanner;

/**
 * Creared with IntelliJ IDEA.
 * Description:【迷宫问题】
 * 定义一个二维数组 N*M ，如 5 × 5 数组下所示：
 * int maze[5][5] = {
 * 0, 1, 0, 0, 0,
 * 0, 1, 1, 1, 0,
 * 0, 0, 0, 0, 0,
 * 0, 1, 1, 1, 0,
 * 0, 0, 0, 1, 0,
 * };
 * 它表示一个迷宫，其中的1表示墙壁，0表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的路线。入口点为[0,0],既第一格是
 * 可以走的路。
 * User:yxd
 * Date:2022-05-21
 * Time:0:24
 */
class Pair{
    int x;
    int y;
    public Pair(int x,int y){
        this.x = x;
        this.y = y;
    }
}
public class Day24_2 {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int row = input.nextInt();
        int col = input.nextInt();
        int[][] nums = new int[row][col];
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                nums[i][j] = input.nextInt();
            }
        }
        boolean[][] bool = new boolean[row][col];
        ArrayList<Pair> path = new ArrayList<>();
        ArrayList<Pair> minPath = new ArrayList<>();
        min_Path(nums,row,col,0,0,bool,path,minPath);
        for(Pair p : minPath){
            System.out.println("(" + p.x + "," + p.y + ")");
        }
    }
//maze迷宫矩阵,row行,col列,x当前位置x值,y当前位置y值,bool标记矩阵,path表示当前路径,minPath表示最短路径
    public static void min_Path(int[][] maze,int row,int col, int x, int y, boolean[][] bool, ArrayList<Pair> path,ArrayList<Pair> minPath){
        //开始判断当前位置是否越界,是否走过,是否是障碍
        if(x < 0 || x >= row || y < 0 || y >= col || bool[x][y] || maze[x][y] == 1){
            //表示当前方向无法走下去,需要看其他方向
            return;
        }
        bool[x][y] = true;
        path.add(new Pair(x,y));
        if(x == row - 1 && y == col - 1){
            if(minPath.isEmpty() || path.size() < minPath.size()){
                minPath.clear();
                for(Pair p : path){
                    minPath.add(p);
                }
            }
        }
        //走四个方向
        min_Path(maze,row,col,x + 1,y,bool,path,minPath);
        min_Path(maze,row,col,x - 1,y,bool,path,minPath);
        min_Path(maze,row,col,x,y + 1,bool,path,minPath);
        min_Path(maze,row,col,x,y - 1,bool,path,minPath);
        //走到这表示当前四个方向都走过但是都走不下去,需要回退
        path.remove(path.size() - 1);
        bool[x][y] = false;

    }
}
